20 低级程序设计

发表于   |   分类于   |  

说明：位操作和其他一些低级运算在编写系统程序（包括编译器和操作系统）、加密程序、图形程序以及其他一些需要高执行速度或高效地使用空间的程序时非常有用。

20.1 按位运算符

说明：C语言一共提供了6个按位运算符。

20.1.1 移位运算符

说明：移位运算符可以改变数的二进制形式，将它的位向左或向右移动。
优先级：低于算数运算符i<<2+1 <==> i<<(2+1)
操作数类型要求：可以是任意整型或字符型的
副作用：不存在（不会改变操作数本身）
|运算符|名称|示例|返回值|复合移位运算符|
|-|-|-|-|-|
|<<|左位移|i<<j|i中的位左移j位的结果（左端溢出，右端补0）|<<=|
|>>|右位移|i>>j|i中的位右移j位的结果（右端溢出，左端补0或保存符号位而补1）|>>=|

1
2
3
4
unsigned int i, j;
i = 13; // 0000000000001101(16位)
j = i << 2; // 0000000000110100(16位)
j = i >> 2; // 0000000000000011(16位)

20.1.2 按位求反、按位与、按位亦或、按位或

优先级：~ > & > ^ > |，都比关系运算符和判等运算符低。
技巧：使用~创建在位一级具备可移植性的程序（例子）

  1. ~0：所有位都为1的整数（否则就要最大的整数，但不同位的机器不同）
  2. ~0x001f：除了最后5位其它为都为1
    |符号|名称|返回值|复合运算符|
    |-|-|-|-|
    |~|按位求反|将每一个0替换成1，每一个1替换成0|~=|
    |&|按位与|对两个操作数相应的位执行逻辑与运算|&=|
    |^|按位亦或|对两个操作数相应的位执行逻辑或操作，都是1时产生0|^=|
    |\|按位或|对两个操作数相应的位执行逻辑或操作，都是1时产生1|\=|
1
2
3
4
5
6
7
8
9
10
11
12
13
// 假设unsigned int类型的值占16位
i = 21; //    0000000000010101
j = 56; //    0000000000111000
k = ~i; //    1111111111101010
k = i & j; // 0000000000010000
k = i ^ j; // 0000000000101101
k = i | j; // 0000000000111101

i = 21;
j = 56;
i &= j;
i ^= j;
i |= j;

20.1.3 用按位运算符访问位

说明：通过按位运算，可以提取或修改存储在少数几个位中的数据。
用途：比如，在编写图形程序时，可能会需要讲两个或更多的像素挤在一个字节中，从而降低空间复杂度和时间复杂度。
方式：构造“掩码”，通过按位复合运算修改位

设置位（为1）

说明： 通过与“掩码”进行按位或运算设置某一位为1
掩码：除要设置的位外都为0（可以通过对整数1进行移位运算构造掩码）（0000000000001000）。
相关按位运算：按位或运算

1
2
3
4
5
6
7
8
9
i = 0x0000;
// 将第4位设置为1
// 0000000000000000 (i)
// 0000000000001000 (掩码)
// 0000000000001000 (按位或运算结果)
i |= 0x0010;

// 更通用的方式,通过移位运算灵活构造掩码
i |= 1 << j; // 使用移位运算构造掩码

将位清零

说明：通过与“掩码”进行按位且运算设置某一位为0
掩码：除要清零的位外都为1的掩码（可以通过移位运算和按位非运算）构造（1111111111110111）。
相关按位运算：按位且运算

1
2
3
4
5
6
7
8
9
i = 0x00ff;  // 0000000011111111

// 0000000011111111（i）
// 1111111111110111 (掩码)
// 0000000011110111 (按位且运算结果)
i &= ~0x0010;

// 更通用的方式,通过移位运算和按位非灵活构造掩码
i &= ~(1 << j);

检测位

说明：检测某一位是否被设置过（设置为1）。
掩码：除要设置的位外都为0（可以通过对整数1进行移位运算构造掩码）（1111111111110111）。
相关按位运算：按位且运算

1
2
3
4
5
6
// 设置需要的掩码(假设在16位机器上)
enum {
	BLUE = 1, // 0000000000000001
	GREN = 2, // 0000000000000010
	RED = 4   // 0000000000000100
};
1
2
3
4
5
6
7
8
9
10
11
i |= BULE; // 设置BLUE bit(最后一位为1)
i &= ~BLUE; // 抹掉BLUE bit

// 检测BLUE bit是否被设置
if (i & BULUE) {
	...
}
// 检测BLUE bit和GREEN bit是否都被设置了
if (i & (BLUE | GREEN)) {
	...
}

20.1.4 用按位运算符访问位域

位域：连续的几个位
位域下标记法：最右边是最低位，记为0位

修改位域

说明：不同于修改位，修改位域并不单纯的只是设置位或清除位，目标值中1和0可以并存，因此多了清除先清除位域的操作。
相关按位运算：按位与（用来清除位域）；按位或（用来将新的位存入域）

1
2
3
4
5
6
7
8
9
/*将二进制的值101存入变量i的第4-6位*/
// 0000000000000000，i的值可以使任意的16位整数
i = 0;

// 先将i的4-6位清零，然后用构造的掩码设置4-6位
// 0000000001110000 (0x0070)
// 1111111110001111 (~0x0070，掩码)
// 0000000001010000 (0x0050，4-6位上为要存储的二进制)
i = i & ~0x0070 | 0x0050
1
2
3
4
/*让上名的例子更加通用*/
// 0000000000000101, 包含需要存储的值
j = 5;
i = (i & ~0x0070) | (j << 4);

获取位域

说明：获得指定位域上的值。
相关按位运算：按位与
技巧：当位域处在数的末尾区间时，获取值更加方便。如果要获取的位域不在末尾，可以先通过位移移至末尾。

1
2
// 0000000000000111 (0x0007)
j = i & 0x0007; // 获取0-2位上的位并放在j的末端
1
j = (i >> 4) & 0x0007;

20.1.5 程序：XOR加密

说明：将每一个字符与一个密匙进行亦或（XOR）运算；要将信息解码，只需要再次加密，即可得到原来的字符。
注意：读或写包含控制字符的文件时会在一些操作系统中引发错误，应当避免。

1
2
3
4
5
6
7
8
-------------加密---------------
		01111010 (z， 加密前)
^(XOR)  00100110 (&, 密匙)
		01011100 (\, 加密后)
-------------解密---------------
		01011100 (\, 解密)
^(XOR)  00100110 (&, 同样的密匙)
		01111010 (z, 解密后)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 以文件作为输入，使用XOR加密(或解密)。并将加密(或解密)后的文本输出
 */
# include <ctype.h>
# include <stdio.h>
# define KEY '&'
int main () {
	int orig_char, new_char;
	// 遍历输入流中的每一个字符，加密后输出，直到文件末尾
	while ((orig_char = getchar()) != EOF) {
		// 加密
		new_char = orig_char ^ KEY;

		// 如果加密（或解密）后的字符是控制字符则不加密（或解密）
		if (iscntrl(orig_char) || iscntrl(new_char)) {
			putchar(orig_char);
		}
		else {
			putchar(new_char);
		}
	}
	return 0;
}
1
$ ./xor < msg.txt

20.2 结构中的位域

说明：C语言提供了可以在结构中声明存储在位域中的成员。
语法：位域的类型必需是int、unsigned int或signed int。

1
2
3
4
struct 结构名 {
	{int|unsigned int|signed int} [成员名]: 位数;
	...
};

注意：使用按位运算可以达到同样的效果，而且可能更快些，当可读性不如结构中的位域。
局限性：通常位域没有地址，因此C语言不允许将&运算符或scanf函数用于位域。
可移植性技巧：将所有的位域声明为unsigned int或signed int而不是int，因为一些编译器将位域的最高位作为符号位，而其它一些编译器则不会。

1
2
3
4
5
6
7
8
9
10
11
/*
* 文件创建日期信息（成员为位域的结构）
*/
struct file_date {
	// 日：5个位
	unsigned int day: 5;
	// 月：5个位
	unsigned int mounth: 4;
	// 年：7个位
	unsigned int year: 7;
};

位域是如何存储的

存储单元：一个存储单元的大小是由实现定义的，通常是8位、16位或32位。
未命名为域：将无法被赋值和使用，但正常占据空间。经常用来作为成员间的填充，以保证其它位域存储在适当的位置。
长度为0的位域：告诉编译器将下一个位域放在一个存储单元的起始位置，即如果当前存储单元还有空间剩余，无论能否放下长度为0的成员的后面的成员，都会将其放在下一个存储单元中。

  • 存储顺序：当编译器处理结构实例时，会将位域逐个存入存储单元（从左向右或从右向左）
  • 位域型成员之间的间隙：位域之间没有间隙，直到剩下的空间不够放下一个位域（这时会跳到下一个存储单元继续存放，即存在间隙或跨存储单元存放，即没有间隙）。

案例

说明：假设位域是从右至左存储，且当一个存储单元剩余的空间无法存储下一个位域成员时会跨存储单元存储。这时DOS系统上编译常用的方式。

1
2
3
4
5
// 声明结构实例
struct file_date fd;
fd.day = 28;
fd.month = 12;
fd.year = 8;
* year month day
存储 0001000 1100 11100
大小（bit） 7 4 5
区间 15-9 8-5 4-0

20.3 其他低级技术

20.3.1 定义依赖机器的类型

说明：可以将char作为一个字节（不一定存储字符）来使用。

1
2
typedef unsigned char BYTE;
typedef unsigned int WORD;

20.3.2 用联合从多个视角看待数据

案例一：使用联合结合结构体（位域成员）实现文件日期和整数的转换。

说明：

  • 获取：可以通过成员i以两个字节的形式获得日期的整数形式
  • 设置：可以通过成员fd以结构体的方式设置文件日期（以两个字节的方式存储）

文件日期定义

1
2
3
4
5
6
7
8
9
10
11
/*
* 文件创建日期信息（成员为位域的结构）
*/
struct file_date {
	// 日：5个位
	unsigned int day: 5;
	// 月：5个位
	unsigned int mounth: 4;
	// 年：7个位
	unsigned int year: 7;
};

封装一个方便读取和设置数据结构

1
2
3
4
union int_date {
	unsigned int ;
	struct file_date fd;
};

实践

1
2
3
4
5
6
7
8
9
10
/**
* 将整数形式（两个字节）的日期以作为文件日期数据结构打印
* @param {undesigned int} n 存储这日期信息的整数
*/
void print_date (undesigned int n) {
	union int_date u;
	u.i = n;
	// 年只显示后两位（比如1990年简称90年）
	printf("%d/%d/%.2d\n", u.fd.month, u.fd.day, (u.fd.year + 1980));
};

案例二：模拟对寄存器的访问（Intel 80x86）

说明：需要对16位寄存器和8位寄存器进行访问，同时保留它们之间的关系。
寄存器：Intel 80x86处理器包涵4个16位的寄存器（AX(AH|AL)、BX(BH|BL)、CX(CH|CL)、DX(DH|DL)），其中每个16位寄存器都包含2个8位寄存器。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef unsigned char BYTE;
typedef unsigned int WORD;

union {
	// 16位寄存器的结构
	struct {
		WORD ax, bx, cx. dx;
	} word;
	
	// 8位寄存器的结构
	struct {
		BYTE al, ah, bl, bh, cl, ch, dl, dh;
	};
} regs;
1
2
3
4
5
6
// 按照8位寄存器的方式修改
regs.byte.ah = 0x12;
regs.byte.al = 0x34;

// 按照16位寄存器的方式观察
printf("AX: %x\n", regs.word.ax);

20.3.3 将指针作为地址使用（将地址转换为指针使用）

说明：指针按照其自身的构造方式可以分为两类（以16位机器为例）
|分类|组成|大小(bit)|地址转换为指针|情景|
|-|-|-|-|
|近指针|偏移量||16|将整数强制转换为指针|在一些计算机中|
|远指针|段地址＋偏移量|32|far(关键字，非标准c)+MK_FP(dos.h中的宏)|Intel CPU的实时模式（DOS使用的模式）|

1
2
3
// 近指针
BYTE *p;
p = (BYTE *) 0x1000; // 将16位整数地址直接转换为指针
1
2
3
// 远指针
BYTE far *p; // 使用far声明一个远指针
p = MKFP(segment, offset); // 段地址， 偏移量

20.3.4 程序：设置Num Lock 键

说明：在IBM PC机极其兼容机上，Num Lock切换涌来确定数字键盘上的按键是作为数字键使用，还是作为移动光标的方向键。
原理：Num Lock的状态保存在地址位地址段为40（16进制）、偏移量为17（16进制）的字节中。该字节的第5位（最低位为0位）用来控制Num Lock的状态。

开启Num Lock

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * 开启num lock
 */
# include <dos.h>

typedef unsigned char BYTE;

int main () {
	BYTE far *p = MK_FP(0x0040, 0x0017);

	// 0000000000100000 (掩码)
	*p |= 0x20; 
	return 0;
}

关闭Num Lock

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * 关闭num lock
 */
# include <dos.h>

typedef unsigned char BYTE;

int main () {
	BYTE far *p = MK_FP(0x0040, 0x0017);

	// 1111111111011111 (掩码)
	*p &= ～0x20; 
	return 0;
}

20.3.5 volatile类型限定符

关键字：volatile
说明：通常使用在用于指向易变内存空间的指针的声明中。用来防止编译器优化过程中错误地将易变内容缓存在了寄存器中，而不再读取内存中易变内容。

优化前的逻辑

1
2
3
4
5
6
7
8
// 优化前的逻辑
while (缓冲区未满) {
	等待输入; // 将输入存储到*p
	buffer[i] = *p;
	if (buffer[i++] == '\n') {
		break;
	}
}

优化后的逻辑

说明：注意到这个循环中既没有改变p，也没有改变p，因此对程序进行优化，使p只被读取一次。

1
2
3
4
5
6
7
8
在寄存器中存储*p;
while (缓冲区未满) {
	等待输入;
	buffer[i] = 存储在寄存器中的值;
	if (buffer[i++] == '\n') {
		
	}
}